/*
 * Scheduler
 *
 * SJSU CS 149 Spring 2009 Project
 *
 * Copyright 2009 Timmy Yee
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

import java.util.Queue;
import java.util.PriorityQueue;
import java.util.Comparator;

import java.util.List;
import java.util.LinkedList;

/**
 * The Scheduler class simulates a process scheduler. The process scheduler
 * decides which process should be run and keep track of which queue each
 * process is in. Each queue can be said to implicitly hold a process
 * state. For example, any processes in the ready queue are in ready state,
 * which means that they are waiting to use the processor. The class also
 * keeps track of what algorithm is being used for the simulation.
 *
 * @author Keven Wong
 * @author Timmy Yee
 */
public final class Scheduler
{
    private static final int MEMORY_SIZE = 256;
    private static final double MAX_RATIO = 0.333333;
    private static List<Integer> frames_;
    private static Queue<Process> jobQ_;
    private static Queue<Process> stallQ_;
    private static Queue<Process> readyQ_;
    private static Queue<Process> diskQ_;
    private static Queue<Process> printerQ_;
    private static Queue<Process> finishQ_;
    private static Algorithm processAlgorithm_ = Algorithm.ROUND_ROBIN;
    private static Algorithm memoryAlgorithm_ = Algorithm.CLOCK;
    private static double totalSkipTime_;

    /**
     * A private constructor to prevent instantiating this static class.
     */
    private Scheduler() {}

    /**
     * Initializes the Scheduler class. This method may also be used to
     * reset the state of the class.
     */
    public static void initialize()
    {
        jobQ_ = new PriorityQueue<Process>(11, new Comparator<Process>() {
            public int compare(Process p1, Process p2) {
                if (p1.getArrivalTime() < p2.getArrivalTime())
                    return -1;
                else if (p1.getArrivalTime() > p2.getArrivalTime())
                    return 1;
                else
                    return 0;
            }
        });

        if (processAlgorithm_ == Algorithm.ROUND_ROBIN)
            readyQ_ = new LinkedList<Process>();
        else // if priority scheduling
            readyQ_ = new PriorityQueue<Process>(11, new Comparator<Process>() {
                public int compare(Process p1, Process p2) {
                    if (p1.getPriority() < p2.getPriority())
                        return -1;
                    else if (p1.getPriority() > p2.getPriority())
                        return 1;
                    else
                        return 0;
                }
            });

        stallQ_ = new LinkedList<Process>();
        diskQ_ = new LinkedList<Process>();
        printerQ_ = new LinkedList<Process>();
        finishQ_ = new LinkedList<Process>();

        frames_ = new LinkedList<Integer>();
        for (int i = 0; i < MEMORY_SIZE; i++)
            frames_.add(i);

        totalSkipTime_ = 0;
    }

    /**
     * Gets the current process scheduling algorithm.
     *
     * @return The current process scheduling algorithm in use.
     */
    public static Algorithm getProcessAlgorithm()
    {
        return processAlgorithm_;
    }

    /**
     * Sets the current process scheduling algorithm.
     *
     * @param algorithm The process scheduling algorithm to use.
     */
    public static void setProcessAlgorithm(Algorithm algorithm)
    {
        processAlgorithm_ = algorithm;
    }

    /**
     * Gets the current memory management algorithm.
     *
     * @return The current memory management algorithm in use.
     */
    public static Algorithm getMemoryAlgorithm()
    {
        return memoryAlgorithm_;
    }

    /**
     * Sets the current memory management algorithm.
     *
     * @param algorithm The memory management algorithm to use.
     */
    public static void setMemoryAlgorithm(Algorithm algorithm)
    {
        memoryAlgorithm_ = algorithm;
    }

    /**
     * Adds a process to the job queue.
     *
     * @param p The process to add.
     */
    public static void add(Process p)
    {
        jobQ_.offer(p);
    }

    /**
     * Adds a process to the ready queue.
     *
     * @param p The newly created process.
     */
    public static void offerToReadyQ(Process p)
    {
        p.setEnterTime();
        readyQ_.offer(p);
    }

    /**
     * Removes a process from the ready queue.
     *
     * @return The process that was removed, or null if ready queue is empty.
     */
    public static Process pollFromReadyQ()
    {
        Process p = readyQ_.poll();

        if (p != null)
            p.setLeaveTime();

        return p;
    }

    /**
     * Checks if there are any processes in any of the active queues.
     *
     * @return True if processes are in any queues
     *         (except for the finish queue), false otherwise.
     */
    public static boolean areProcessesActive()
    {
        return !jobQ_.isEmpty() || !readyQ_.isEmpty() ||
               !diskQ_.isEmpty() || !printerQ_.isEmpty() ||
               Processor.isRunning();
    }

    /**
     * Checks whether a process is ready to be put into the new queue.
     *
     * @return True if a process is ready to be created, false otherwise.
     */
    private static boolean hasNewProcessArrived()
    {
        double time = Simulator.getCurrentTime();

        if (jobQ_.peek() == null)
            return false;

        return Util.areDoublesEqual(time, jobQ_.peek().getArrivalTime());
    }

    /**
     * Creates a new process if a process is
     * ready to be put into the ready queue.
     */
    public static void checkForNewArrival()
    {
        if (!hasNewProcessArrived())
            return;

        Process p = jobQ_.poll();
        Trace.log("New process (%d) arrives", p.getId());

        try {
            createProcess(p);
        } catch (IllegalStateException e) {
            Trace.log("Process %d is stalled " +
                        "due to the lack of available frames", p.getId());
            stallQ_.offer(p);
        }
    }

    /**
     * Moves a process from new queue and puts it into ready queue. This
     * method will also allocate the necessary frames for a the process.
     * <p>
     * Note that this is a simulated process creation.
     *
     * @param p The process to create.
     * @throws IllegalStateException If there aren't enough frames to
     *                               allocate to the process.
     */
    private static void createProcess(Process p)
    {
        int maxPages = (int) Math.round(p.getSize() * MAX_RATIO);

        if (p.isMemoryEnabled())
            if (maxPages > frames_.size())
                throw new IllegalStateException();

        p.setCreationTime();
        Trace.log("Process %d transferred from Job Queue " +
                    "to Ready Queue", p.getId());

        if (p.isMemoryEnabled()) {
            p.setFrames(new LinkedList<Integer>(frames_.subList(0, maxPages)));
            Trace.log("Allocated %d pages to process %d",
                        maxPages, p.getId());

            // remove allocated frames from frames list
            frames_.subList(0, maxPages).clear();
        }

        offerToReadyQ(p);
    }

    /**
     * Inserts the running process into the finish queue. This method also
     * gets back all the allocated frames from the process.
     * <p>
     * Note that this is a simulated process termination.
     */
    public static void buryProcess()
    {
        Process p = Processor.getRunningProcess();

        if (p.isMemoryEnabled()) {
            frames_.addAll(p.getFrames());

            try {
                createProcess(stallQ_.peek()); // operation may fail
                stallQ_.poll(); // if successful, remove process from stallQ
            } catch (NullPointerException e) {
                // nothing in the stall queue; move along
            } catch (IllegalStateException e) {
                // not enough memory; keep stalling
            }
        }

        finishQ_.offer(p);
    }

    /**
     * Swaps the running process with one from the ready queue.
     */
    public static void swapProcesses()
    {
        Process old = Processor.getRunningProcess();

        if (old.isDone())
            Processor.killRunningProcess();
        else
            offerToReadyQ(old);

        Processor.setRunningProcess();
    }

    /**
     * Assigns possibly a process into a device queue. If there is an
     * assignment, then a new running process is set.
     *
     * @param p The process to be assigned to a device.
     * @return True if the process was assigned, false otherwise.
     */
    public static boolean assignToDevice(Process p)
    {
        String oper, device;
        Device d = p.getDeviceRequest();

        if (d == null)
            return false;

        if (d == Device.DISK) {
            p.startDiskOperation();
            diskQ_.offer(p);
            oper = "disk";
            device = "Disk";
        } else if (d == Device.PRINTER) {
            p.startPrintOperation();
            printerQ_.offer(p);
            oper = "print";
            device = "Printer";
        } else
            throw new IllegalArgumentException("invalid device");

        Trace.log("Trap instruction (%s system call) occurred", oper);
        Trace.log("Process %d requests %s operation", p.getId(), oper);
        Trace.log("Process %d added to %s Queue", p.getId(), device);

        Processor.setRunningProcess();
        return true;
    }

    /**
     * Gets a process out of the device queue if finished with the request.
     *
     * @param d   The device to get a possible process from.
     * @return    If finished, the process that is ready to be put back into
     *            the ready queue, null otherwise.
     */
    public static Process getProcessFromDeviceQ(Device d)
    {
        Queue<Process> q;

        if (d == Device.DISK)
            q = diskQ_;
        else if (d == Device.PRINTER)
            q = printerQ_;
        else
            throw new IllegalArgumentException("invalid device");

        Process p = q.peek();

        if (p == null)
            return null;

        if (Util.areDoublesEqual(p.getDeviceTime(), 0))
            return q.poll();
        else {
            p.useDevice(Simulator.TIME_UNIT);
            return null;
        }
    }

    /**
     * Creates a string that describes a queue's content.
     *
     * @param name  The name of the queue.
     * @param q     The process queue itself.
     * @return      A string that shows each process in the queue.
     */
    private static String createQueueString(String name, Queue<Process> q)
    {
        List<String> parts = new LinkedList<String>();

        for (Process p : q)
            parts.add(String.format("%d(%.1f)", p.getId(),
                                    p.getRemainingWork()));

        return String.format("\t%s: %s\n", name, Util.join(parts, ", "));
    }

    /**
     * Gets the contents of the ready, disk, and printer queues.
     *
     * @return A string that contains contents of the three main queues.
     */
    public static String getPageTable()
    {
        List<String> parts = new LinkedList<String>();

        for (Process p : readyQ_)
            parts.add(p.getPageTable());

        for (Process p : diskQ_)
            parts.add(p.getPageTable());

        for (Process p : printerQ_)
            parts.add(p.getPageTable());

        return String.format("\tInverted page table: %s\n",
                             Util.join(parts, ", "));
    }

    /**
     * Gets the percentage of the free frames of the system.
     *
     * @return A string that contains the free frames percentage.
     */
    public static String getFreeFramesPercent()
    {
        return String.format("\tFree frames percentage: %.1f%%%%\n",
                             (double) frames_.size() / MEMORY_SIZE * 100);
    }

    /**
     * Gets the contents of the ready, disk, and printer queues, the
     * inverted page table, and the free frames percentage.
     *
     * @return A string that contains info from various data structures.
     */
    public static String getInfo()
    {
        String content = "Simulator information:\n";

        content += "\n\t[ Queues content (remaining CPU time) ]\n";
        content += createQueueString("Ready Q", readyQ_);
        content += createQueueString("Disk Q", diskQ_);
        content += createQueueString("Printer Q", printerQ_);
        content += "\n\t[ Memory management information ]\n";
        content += getPageTable();
        content += getFreeFramesPercent();

        return content;
    }

    /**
     * Gets the average of the times according to the given type
     * that are stored in all of the processes.
     *
     * @param t The kind of time to get.
     * @return The average time.
     */
    public static double getAverage(Time t)
    {
        double sum = 0;

        for (Process p : finishQ_)
            sum += p.getTime(t);

        return sum / finishQ_.size();
    }

    /**
     * Gets the average page faults per second of all the processes.
     *
     * @return The average page faults per second.
     */
    public static double getAverageFaultsPerSecond()
    {
        double sum = 0;

        for (Process p : finishQ_)
            sum += p.computeFaultsPerSecond();

        return sum / finishQ_.size();
    }

    /**
     * Gets the CPU utilization percentage of all the processes.
     *
     * @return The CPU utilization percentage.
     */
    public static double getUtilPercent()
    {
        double sum = 0;
        for (Process p : finishQ_)
            sum += p.getProcessingTime();
        double totalProcTime = sum / finishQ_.size();

        sum = 0;
        for (Process p : finishQ_)
            sum += p.getIdleTime();
        double totalIdleTime = sum / finishQ_.size() + totalSkipTime_;

        return totalProcTime / (totalProcTime + totalIdleTime) * 100;
    }

    /**
     * If processes are only active in the device queues,
     * then optimize the main loop by fast-forwarding time.
     *
     * @return New current time, or 0 if no skipping of time has been done.
     */
    public static double possiblySkipTime()
    {
        if (Processor.isRunning() ||
            !readyQ_.isEmpty() ||
            !areProcessesActive())
            return 0;

        double newProcTime, diskProcTime, printProcTime, skipTime;
        double currentTime = Simulator.getCurrentTime();
        double interval = Display.getDisplayInterval();

        Process newProc = jobQ_.peek();
        Process diskProc = diskQ_.peek();
        Process printProc = printerQ_.peek();

        if (newProc == null)
            newProcTime = Double.POSITIVE_INFINITY;
        else
            newProcTime = newProc.getArrivalTime() - currentTime;

        if (diskProc == null)
            diskProcTime = Double.POSITIVE_INFINITY;
        else
            diskProcTime = diskProc.getDeviceTime();

        if (printProc == null)
            printProcTime = Double.POSITIVE_INFINITY;
        else
            printProcTime = printProc.getDeviceTime();

        skipTime = Math.min(newProcTime, diskProcTime);
        skipTime = Math.min(skipTime, printProcTime);
        skipTime = Math.min(skipTime, interval - (currentTime % interval));

        if (skipTime == Double.POSITIVE_INFINITY)
            return 0;

        if (diskProc != null)
            diskProc.useDevice(skipTime);
        if (printProc != null)
            printProc.useDevice(skipTime);

        Trace.log("Fast forward time...");
        totalSkipTime_ += skipTime;
        return currentTime + skipTime;
    }

    /**
     * Activates some process to run.
     * <p>
     * The scheduler will choose the appropriate process to run according
     * to whether the processor has no process and if the algorithm is
     * preemptive.
     */
    public static void activate()
    {
        if (!Processor.isRunning())
            Processor.setRunningProcess();

        if (processAlgorithm_ == Algorithm.PREEMPT &&
            readyQ_.peek() != null && Processor.isRunning() &&
            readyQ_.peek().getPriority() < Processor.getRunningPriority())
            swapProcesses();

        Processor.run();
    }
}

